package at.fhhgb.mc.Aufgabe01;

public class BinarySearchTree {

	/** Inner class for the binary tree node. **/
	protected class BinaryTreeNode {
		public BinaryTreeNode left;
		public BinaryTreeNode right;
		public int data;

		public BinaryTreeNode(int elem) {
			data = elem;
			left = null;
			right = null;
		}

		public BinaryTreeNode(int data, BinaryTreeNode left,
				BinaryTreeNode right) {
			this.data = data;
			this.left = left;
			this.right = right;
		}

		public BinaryTreeNode() {
			this.data = 0;
			this.left = null;
			this.right = null;
		}

	}

	/** Root node of the tree. **/
	protected BinaryTreeNode root;

	/** Number of elements stored in the tree. */
	protected int size;

	private static boolean isFirst = false;

	/**
	 * Inserts the given element. Duplicate elements are not allowed. Returns
	 * true if insertion was successful, false otherwise.
	 */
	public boolean insert(int elem) {
		if (add(root, null, false, elem) == true) {
			return true;
		} else {
			return false;
		}
	}

	private boolean add(BinaryTreeNode t, BinaryTreeNode parent, boolean right,
			int elem) {
		if (t == null) {
			BinaryTreeNode n = new BinaryTreeNode(elem, null, null);
			// size++;
			if (root == t) {
				root = n;
				return true;
			}
			if (right) {
				parent.right = n;
			} else {
				parent.left = n;
			}
			return true;
		} else if (t.data == elem) {
			return false;
		} else if (elem < t.data) {
			return add(t.left, t, false, elem);
		} else {
			return add(t.right, t, true, elem);
		}
	}

	/**
	 * Searches for the (first) element with the given key. Returns true if it
	 * could be found, false otherwise.
	 */
	public boolean find(int key) {
		if (find(root, key) == true) {
			return true;
		} else {
			return false;
		}
	}
	
	private boolean find(BinaryTreeNode t, int elem) {
		if (t == null)
			return false;
		if (t.data == elem)
			return true;
		if (elem < t.data)
			return find(t.left, elem);
		return find(t.right, elem);
	}

	/**
	 * Removes the element with the given key. Returns true if the key could be
	 * found (and removed), false otherwise.
	 */
	public boolean remove(int key) {
		return remove(root, key);
	}

	private boolean remove(BinaryTreeNode t, int key) {
		BinaryTreeNode n, st, par, succ;
		par = null;
		st = t;
		while (st != null && st.data != key) {
			par = st;
			if (key < st.data) {
				st = st.left;
			} else {
				st = st.right;
			}
		}
		n = st;
		if (n == null) {
			return false;
		}
		if (n.right == null) {
			// no right son
			st = n.left;
		} else if (n.right.left == null) {
			// right son has no left son
			st = n.right;
			st.left = n.left;
		} else {
			// right son has left son
			succ = n.right;
			while (succ.left.left != null)
				succ = succ.left;
			st = succ.left;
			succ.left = st.right;
			st.left = n.left;
			st.right = n.right;
		}
		if (par == null) {
			root = st;
		} else if (key < par.data) {
			par.left = st;
		} else {
			par.right = st;
		}

		return true;
	}

	/** Returns the number of elements stored in the tree. */
	public int size() {
		return size(root);
	}

	private int size(BinaryTreeNode actual) {
		if (actual == null) {
			return 0;
		}
		return 1 + size(actual.left) + size(actual.right);
	}

	/**
	 * Returns the parent element of the given key. Integer.MIN_VALUE if no
	 * parent can be found.
	 */
	public int getParent(int key) {
		return getParent(null, root, key);
	}

	private int getParent(BinaryTreeNode actual, BinaryTreeNode previous,
			int key) {

		if (previous == null)
			return Integer.MIN_VALUE;
		if (previous.data == key) {
			if (root.data == key) {
				return Integer.MIN_VALUE;
			}
			return actual.data;
		}
		if (key < previous.data) {
			return getParent(previous, previous.left, key);
		}
		return getParent(previous, previous.right, key);
	}

	/**
	 * Returns the elements of the tree in ascending (inorder traversal) or
	 * descending (reverse inorder traversal) order.
	 */
	public int[] toArray(boolean ascending) {
		StringBuffer buff = new StringBuffer();
		isFirst = true;
		arrayHelper(buff, root);

		String[] splittArr = buff.toString().split("\\, ");

		int[] array = new int[size()];
		for (int i = 0; i < size(); i++) {
			array[i] = Integer.parseInt(splittArr[i]);
		}

		if (ascending == true) {
			return array;
		}

		// reverse Order
		int temp;
		for (int i = 0; i < size() / 2; i++) {
			temp = array[i];
			array[i] = array[size() - 1 - i];
			array[size() - 1 - i] = temp;
		}
		return array;
	}

	private void arrayHelper(StringBuffer buff, BinaryTreeNode actual) {
		if(actual == null){
			return;
		}
		arrayHelper(buff, actual.left);
		if(isFirst) {
			isFirst = false;
		} else {
			buff.append(", ");
		}
		buff.append(actual.data);
		arrayHelper(buff, actual.right);
		
	}

	/** Returns the elements of the tree (postorder traversal). */
	public int[] toArrayPostOrder() {
		
		StringBuffer buff = new StringBuffer();
		isFirst = true;
		arrayHelperPostOrder(buff,root);
		
		String[] splittArr = buff.toString().split("\\, ");

		int[] array = new int[size()];
		for (int i = 0; i < size(); i++) {
			array[i] = Integer.parseInt(splittArr[i]);
		}
		
		return array;
	}

	private void arrayHelperPostOrder(StringBuffer buff, BinaryTreeNode actual) {
		if(actual == null)
			return;
		arrayHelperPostOrder(buff, actual.left);
		arrayHelperPostOrder(buff, actual.right);
		if(isFirst) {
			isFirst = false;
		} else {
			buff.append(", ");
		}
		buff.append(actual.data);
	}

	/** Returns the elements of the tree (preorder traversal). */
	public int[] toArrayPreOrder() {
		int[] array = new int[size()];
		int index = 0;

		if (size() == 0) {
			return array;
		}

		toArrayPreOrderHelper(array, root, index);
		return array;
	}

	private int toArrayPreOrderHelper(int[] array, BinaryTreeNode actual,
			int index) {
		if (actual == null) {
			return index;
		}

		array[index++] = actual.data;
		index = toArrayPreOrderHelper(array, actual.left, index);
		index = toArrayPreOrderHelper(array, actual.right, index);

		return index;
	}

	/**
	 * Returns largest number stored in the tree. Integer.MIN_VALUE if no
	 * largest element can be found
	 */
	public int max() {
		if (root == null) {
			return Integer.MIN_VALUE;
		}
		int ret = root.data;
		BinaryTreeNode actual = root;
		while (actual.right != null) {
			actual = actual.right;
			ret = actual.data;
		}
		return ret;
	}

	/**
	 * Returns smallest number stored in the tree. Integer.MIN_VALUE if no
	 * smallest element can be found
	 */
	public int min() {
		if (root == null) {
			return Integer.MIN_VALUE;
		}
		int ret = root.data;
		BinaryTreeNode actual = root;
		while (actual.left != null) {
			actual = actual.left;
			ret = actual.data;
		}
		return ret;
	}

	/** Represents the tree in a human readable form. */
	public String toString() {
		System.out.print("Please, turn your head to the left\n\n");
		return toString("", root);
	}

	private static String toString(String prefix, BinaryTreeNode node) {
		if (node == null)
			return "";
		String string = prefix + node.data;
		if (node.right != null)
			string = toString("    " + prefix, node.right) + "\n" + string;
		if (node.left != null)
			string = string + "\n" + toString("    " + prefix, node.left);
		return string;
	}
}